{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Sorting Algorithms\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Present sorting algorithms here primarily to provide some practice in **thinking about algorithm design and complexity analysis**\n",
    "\n",
    "We begin with a simple but **inefficient** algorithm, **selection sort**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Selection sort \n",
    "\n",
    "### 1.1 Selection sort in Python\n",
    "\n",
    "The selection sort algorithm sorts an array by repeatedly finding the **minimum** element (considering ascending order) from **unsorted** part and putting it at the **beginning**. \n",
    "\n",
    "The algorithm maintains two **subarrays** in a given array.\n",
    "\n",
    "1. The subarray which is already `sorted`\n",
    "2. Remaining subarray which is `unsorted`\n",
    "\n",
    "In every iteration of selection sort, the `minimum` element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.\n",
    "\n",
    ">\n",
    ">首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。\n",
    ">\n",
    "Example:\n",
    "```c\n",
    "int a[7] = {7, 4, 5, 9, 8, 2, 1};\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![selsort](./img/ds/selsort.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def select_sort(L):\n",
    "    length=len(L)\n",
    "    # Traverse through all array elements\n",
    "    for i in range(length):\n",
    "        #  [0, i-1] already sort\n",
    "        # Find the minimum element in remaining unsorted array [i, size-1] and swap with L[i]\n",
    "        min_idx = i  # assume fist element is the smallest\n",
    "        for j in range(i+1, length):\n",
    "            if L[j]<L[min_idx] :\n",
    "                min_idx = j\n",
    "        # Swap the found minimum element with  the first element  L[i]      \n",
    "        L[i], L[min_idx] = L[min_idx], L[i]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L=[7, 4, 5, 9, 8, 2, 1]\n",
    "select_sort(L)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The time complexity**\n",
    "\n",
    "For a list of size $n$, the total number of comparisons for a list of size $n$ is the following:\n",
    "\n",
    "$(n-1)+(n-2)+...+1=n(n-1)=\\frac{1}{2}n^2-\\frac{1}{2}n$\n",
    "\n",
    "The complexity of the entire function is $O(n^2)$. \n",
    "\n",
    "**The space complexity**\n",
    "\n",
    "selection sort is an **in-place(原址)** sorting algorithm.\n",
    "\n",
    "Because it works by swapping the place of elements **within** the list, \n",
    "\n",
    "it uses only <b>a constant amount of extra storage</b>: `one` element in our implementation. \n",
    "\n",
    "The space complexity: $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2  SelectionSort in C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/SelectionSort.c\n",
    "\n",
    "/*\n",
    " Sorting an array using Selection Sort (SelectionSort.c) \n",
    "*/\n",
    "\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "\n",
    "void selectionSort(int a[], int size);\n",
    "void print(const int a[], int iMin, int iMax);\n",
    "\n",
    "// Sort the given array of size using selection sort\n",
    "void selectionSort(int a[], int size)\n",
    "{\n",
    "   int temp; // for swaping\n",
    "   for (int i = 0; i < size - 1; ++i)\n",
    "   {\n",
    "      // for tracing\n",
    "      print(a, 0, i - 1);\n",
    "      print(a, i, size - 1);\n",
    "\n",
    "      // [0, i-1] already sort\n",
    "      // Search for the smallest element in  remaining unsorted array [i, size-1] and swap with a[i]\n",
    "      int minIndex = i; // assume fist element is the smallest\n",
    "      for (int j = i + 1; j < size; ++j)\n",
    "      {\n",
    "         if (a[j] < a[minIndex])\n",
    "            minIndex = j;\n",
    "      }\n",
    "      if (minIndex != i)\n",
    "      { // swap\n",
    "         temp = a[i];\n",
    "         a[i] = a[minIndex];\n",
    "         a[minIndex] = temp;\n",
    "      }\n",
    "\n",
    "      // for tracing\n",
    "      printf(\"=> \");\n",
    "      print(a, 0, i - 1);\n",
    "      print(a, i, size - 1);\n",
    "      printf(\"\\n\");\n",
    "   }\n",
    "}\n",
    "\n",
    "// Print the contents of the array in [iMin, iMax]\n",
    "void print(const int a[], int iMin, int iMax)\n",
    "{\n",
    "   printf(\"{\");\n",
    "   for (int i = iMin; i <= iMax; ++i)\n",
    "   {\n",
    "      printf(\"%d\", a[i]);\n",
    "      if (i < iMax)\n",
    "         printf(\",\");\n",
    "   }\n",
    "   printf(\"}\");\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "   const int SIZE = 7;\n",
    "   int a[7] = {7, 4, 5, 9, 8, 2, 1};\n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "   selectionSort(a, SIZE);\n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "\n",
    "   return 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/SelectionSort ./demo/src/SelectionSort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\SelectionSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Merge Sort\n",
    "\n",
    "we can do a lot better than quadratic time$O(n^2)$ using a **divide-and-conquer(分治）** algorithm. It was invented in 1945, by John von Neumann(约翰·冯·诺依曼), and is still widely used.\n",
    "\n",
    "<font color='blue'>**Divide and conquer(分治)**</font> is a technique used for \n",
    "\n",
    "* breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. \n",
    "\n",
    "It can be helpful to think of this method as `divide, conquer, and combine.`\n",
    "\n",
    "\n",
    "**Merge sort** is a prototypical <b>divide-and-conquer algorithm</b>. \n",
    "\n",
    "The key observation made by von Neumann is that **two sorted lists** can be efficiently **merged** into a single sorted list.\n",
    "\n",
    "<font color='blue'>**The merge idea**</font> is: \n",
    "\n",
    "* Look at the **first** element of each list, and move the **smaller of the two** to the **end** of the **result** list.\n",
    "\n",
    "* When one of the lists is empty, all that remains is to copy the remaining items from the other list.\n",
    "\n",
    "This will be the sorted list.\n",
    "\n",
    "Consider, for example, merging the two sorted lists\n",
    "```\n",
    " [1,5,12,18,19,20]\n",
    " [2,3,4,17]\n",
    "```\n",
    "![mergesortedlist](./img/ds/mergesortedlist.png)\n",
    "\n",
    "**The complexity of the `merge` process**\n",
    "\n",
    "It involves two constant-time operations： \n",
    "\n",
    "* 1 comparing the values of elements \n",
    "\n",
    "* 2 copying elements from one list to another. \n",
    "\n",
    "The number of comparisons is **O(len(L))**, where L is the **longer** of the two lists. \n",
    "\n",
    "The number of copy operations is **O(len(L1) + len(L2))**, because each element gets copied exactly once. \n",
    "\n",
    "Therefore, `merging` two sorted lists is **linear** in **the length of the lists**:$O(len(L))$\n",
    "\n",
    "\n",
    "<font color='blue'>**The merge sort**</font> \n",
    "\n",
    "It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.\n",
    "\n",
    "```python\n",
    "MergeSort(arr[], l,  r)\n",
    "   If r > l\n",
    "     1. Find the middle point to divide the array into two halves:  \n",
    "             middle m = l+ (r-l)/2\n",
    "     2. Call mergeSort for first half:   \n",
    "             Call mergeSort(arr, l, m)\n",
    "     3. Call mergeSort for second half:\n",
    "             Call mergeSort(arr, m+1, r)\n",
    "     4. Merge the two halves sorted in step 2 and 3:\n",
    "             Call merge(arr, l, m, r)\n",
    "```   \n",
    ">\n",
    ">合并排序算法是采用分治法（Divide and Conquer）的一个非常典型的应用\n",
    ">* 分割：递归地把当前序列平均分割成两半\n",
    ">* 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）\n",
    ">\n",
    ">把数据分为两段，从两段中逐个选最小/最大的元素移入新数据段的末尾。\n",
    "\n",
    "Like many divide-and-conquer algorithms it is most easily described recursively: \n",
    "\n",
    "1. If the list is of length 0 or 1, it is already sorted. \n",
    "2. If the list has more than one element, split the list into two lists, and use merge sort to sort each of them.\n",
    "3. Merge the results\n",
    "\n",
    "![merge_sort](./img/ds/merge_sort.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The complexity of merge sort** \n",
    "\n",
    "We already know that the time complexity of `merge` process is $O(len(L))$.\n",
    "\n",
    "At each level of `recursion` the total number of elements to be merged is $len(L)$. \n",
    "\n",
    "Therefore, the time complexity of mergeSort is $O(len(L))$ `multiplied` by the number of **levels** of `recursion`. \n",
    "\n",
    "Since mergeSort divides the list <b>in half</b> each time, we know that the number of **levels** of recursion is $O(log(len(L))$. \n",
    "  \n",
    "Therefore, the time complexity of mergeSort is $O(n*log(n))$, where n is len(L).\n",
    "                                                                                   \n",
    "**Space complexity**\n",
    "\n",
    "<b>Merge sort</b> algorithm  involves making <b>copies of the list</b>. This means that its space complexity is $O(n))$.                                                                                   \n",
    "\n",
    "This improvement in time complexity comes with a price: Space complexity: $O(n)$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Merge Sort in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(left, right, compare):\n",
    "    \"\"\"Assumes left and right are sorted lists and\n",
    "         compare defines an ordering on the elements.\n",
    "       Returns a new sorted (by compare) list containing the\n",
    "         same elements as (left + right) would contain.\"\"\"\n",
    "    \n",
    "    result = []  # the copy of the list.\n",
    "    i,j = 0, 0\n",
    "    while i < len(left) and j < len(right):\n",
    "        if compare(left[i], right[j]):\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "    while (i < len(left)):\n",
    "        result.append(left[i])\n",
    "        i += 1\n",
    "    while (j < len(right)):\n",
    "        result.append(right[j])\n",
    "        j += 1\n",
    "    return result\n",
    "\n",
    "def merge_sort(L, compare = lambda x,y:x<y):\n",
    "    \"\"\"Assumes L is a list, compare defines an ordering on elements of L\n",
    "       Returns a new sorted list containing the same elements as L\"\"\"\n",
    "    if len(L) < 2:\n",
    "        return L[:]\n",
    "    else:\n",
    "        middle = len(L)//2\n",
    "        left = merge_sort(L[:middle], compare)\n",
    "        right = merge_sort(L[middle:], compare)\n",
    "        return merge(left, right, compare)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we have made the `comparison` operator a parameter of the `merge_sort` function and written a `lambda` expression to supply a default value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L=[1,5,12,18,19,20,2,3,4,17]\n",
    "L1=merge_sort(L)\n",
    "print(L1)\n",
    "L2=merge_sort(L,lambda x,y:x>y)\n",
    "print(L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 MergeSort in C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/MergeSort.c\n",
    "\n",
    "/* Sorting an array using Merge Sort (MergeSort.c) */\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    " \n",
    "void mSort(int a[], int size);\n",
    "void mergeSort(int a[], int iLeft, int iRight, int work[]);\n",
    "void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,\n",
    "           int iRightHalfLeft, int iRightHalfRight, int work[]);\n",
    "void print(const int a[], int iLeft, int iRight);\n",
    "\n",
    " \n",
    "// Sort the given array of size\n",
    "void mSort(int a[], int size) {\n",
    "   int work[size];  // work space\n",
    "   mergeSort(a, 0, size - 1, work);\n",
    "}\n",
    " \n",
    "// Sort the given array in [iLeft, iRight]\n",
    "void mergeSort(int a[], int iLeft, int iRight, int work[]) {\n",
    "   if ((iRight - iLeft) >= 1) {   // more than 1 elements, divide and sort\n",
    "      // Divide into left and right half\n",
    "      int iLeftHalfLeft = iLeft;\n",
    "      int iLeftHalfRight = (iRight + iLeft) / 2;   // truncate\n",
    "      int iRightHalfLeft = iLeftHalfRight + 1;\n",
    "      int iRightHalfRight = iRight;\n",
    " \n",
    "      // Recursively sort each half\n",
    "      mergeSort(a, iLeftHalfLeft, iLeftHalfRight, work);\n",
    "      mergeSort(a, iRightHalfLeft, iRightHalfRight, work);\n",
    " \n",
    "      // Merge two halves\n",
    "      merge(a, iLeftHalfLeft, iLeftHalfRight, iRightHalfLeft, iRightHalfRight, work);\n",
    "   }\n",
    "}\n",
    " \n",
    "// Merge two halves in [iLeftHalfLeft, iLeftHalfRight] and [iRightHalfLeft, iRightHalfRight]\n",
    "// Assume that iLeftHalfRight + 1 = iRightHalfLeft\n",
    "void merge(int a[], int iLeftHalfLeft, int iLeftHalfRight,\n",
    "           int iRightHalfLeft, int iRightHalfRight, int work[]) {\n",
    "   int size = iRightHalfRight - iLeftHalfLeft + 1;\n",
    "   int iResult = 0;\n",
    "   int iLeft = iLeftHalfLeft;\n",
    "   int iRight = iRightHalfLeft;\n",
    "   while (iLeft <= iLeftHalfRight && iRight <= iRightHalfRight) {\n",
    "      if (a[iLeft] <= a[iRight]) {\n",
    "         work[iResult++] = a[iLeft++];\n",
    "      } else {\n",
    "         work[iResult++] = a[iRight++];\n",
    "      }\n",
    "   }\n",
    "   // Copy the remaining left or right into work\n",
    "   while (iLeft <= iLeftHalfRight) work[iResult++] = a[iLeft++];\n",
    "   while (iRight <= iRightHalfRight) work[iResult++] = a[iRight++];\n",
    " \n",
    "   // for tracing\n",
    "   print(a, iLeftHalfLeft, iLeftHalfRight);\n",
    "   print(a, iRightHalfLeft, iRightHalfRight);\n",
    "   printf(\"=> \");\n",
    "   print(work, 0, size - 1);\n",
    "   printf(\"\\n\");\n",
    " \n",
    "   // Copy the work back to the original array\n",
    "   for (iResult = 0, iLeft = iLeftHalfLeft; iResult < size; ++iResult, ++iLeft) {\n",
    "      a[iLeft] = work[iResult];\n",
    "   }\n",
    "}\n",
    " \n",
    "// Print the contents of the given array from iLeft to iRight (inclusive)\n",
    "void print(const int a[], int iLeft, int iRight) {\n",
    "   printf(\"{\");\n",
    "   for (int i = iLeft; i <= iRight; ++i) {\n",
    "      printf(\"%d\", a[i]);\n",
    "      if (i < iRight) printf(\",\");\n",
    "   }\n",
    "   printf(\"} \");\n",
    "}\n",
    "\n",
    " \n",
    "int main() {\n",
    "   // Test 1\n",
    "   const int SIZE_1 = 8;\n",
    "   int a1[8] = {8, 4, 5, 3, 2, 9, 4, 1};\n",
    " \n",
    "   print(a1, 0, SIZE_1 - 1);\n",
    "   printf(\"\\n\");\n",
    "   mSort(a1, SIZE_1);\n",
    "   print(a1, 0, SIZE_1 - 1);\n",
    "   printf(\"\\n \\n\");\n",
    "\n",
    "    \n",
    "   return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/MergeSort ./demo/src/MergeSort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\MergeSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Quick sort\n",
    "\n",
    "Quicksort uses `divide` and `conquer` to sort an array. \n",
    "\n",
    "Here are the divide, conquer, and combine steps that quicksort uses:\n",
    "\n",
    "**Divide**\n",
    "\n",
    "1. Pick a pivot element, $A[q]$\n",
    "\n",
    "2. Partition, or rearrange, the array into two subarrays: $A[p,…,q−1]$ such that all elements are less than $A[q]$, and $A[q+1,…,r]$ such that all elements are greater than or equal to $A[q]$.\n",
    "\n",
    "**Conquer**: \n",
    "\n",
    "Sort the subarrays $A[p,…,q−1]$ and $A[q+1,…,r]$ recursively with `quicksort`.\n",
    "\n",
    "**Combine**: \n",
    "\n",
    "No work is needed to combine the arrays because they are already sorted\n",
    "\n",
    ">快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。\n",
    ">\n",
    ">步骤为：\n",
    ">\n",
    ">* 挑选基准值：从数列中挑出一个元素，称为\"基准\"（pivot)\n",
    ">* 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;\n",
    ">* 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。\n",
    ">\n",
    ">递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。\n",
    ">\n",
    ">选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。\n",
    "\n",
    "\n",
    "![quick-sort](./img/ds/quick-sort.jpg)\n",
    "\n",
    "**Complexity**\n",
    "\n",
    "* The worst-case time complexity is $O(n^2)$. The average-case (typical) and best-case is $O(nlogn)$. \n",
    "\n",
    "* **In-place** sorting can be achieved without additional space requirement.\n",
    "\n",
    "![quick-sort](./img/ds/quicksort-1.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1  Quick Sort in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(array):\n",
    "    less = []\n",
    "    pivotList = []\n",
    "    more = []\n",
    "\n",
    "    if len(array) <= 1:\n",
    "        return array\n",
    "    else:\n",
    "        pivot = array[0]\n",
    "        for i in array:\n",
    "            if i < pivot:\n",
    "                less.append(i)\n",
    "            elif i > pivot:\n",
    "                more.append(i)\n",
    "            else:\n",
    "                pivotList.append(i)\n",
    "        less = quick_sort(less)\n",
    "        more = quick_sort(more)\n",
    "        return less + pivotList + more"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array=[49, 38,65, 97,76, 13, 27,49]\n",
    "sortedarray=quick_sort(array)\n",
    "print(sortedarray)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Quick Sort in C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "```cpp\n",
    "// Sort the given array in [left, right]\n",
    "void quickSort(int a[], int left, int right) {\n",
    "   if ((right - left) >= 1) {   // more than 1 elements, need to sort\n",
    "      choosePivot(a, left, right);\n",
    "      int pivotIndex = partition(a, left, right);\n",
    "      quickSort(a, left, pivotIndex -  1);\n",
    "      quickSort(a, pivotIndex + 1, right);\n",
    "   }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/QuickSort.c\n",
    "/* \n",
    " Sorting an array using Quick Sort (QuickSort.c) \n",
    "\n",
    "*/\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    " \n",
    "void quickSort(int a[], int size);\n",
    "void quick_Sort(int a[], int left, int right);\n",
    "void choosePivot(int a[], int left, int right);\n",
    "int partition(int a[], int left, int right);\n",
    "void print(const int a[], int left, int right);\n",
    " \n",
    "// Sort the given array of size\n",
    "void quickSort(int a[], int size) {\n",
    "   quick_Sort(a, 0, size - 1);\n",
    "}\n",
    " \n",
    "// Sort the given array in [left, right]\n",
    "void quick_Sort(int a[], int left, int right) {\n",
    "   if ((right - left) >= 1) {   // more than 1 elements, need to sort\n",
    "      choosePivot(a, left, right);\n",
    "      int pivotIndex = partition(a, left, right);\n",
    "      quick_Sort(a, left, pivotIndex -  1);\n",
    "      quick_Sort(a, pivotIndex + 1, right);\n",
    "   }\n",
    "}\n",
    " \n",
    "// Choose a pivot element and swap with the right\n",
    "void choosePivot(int a[], int left, int right) {\n",
    "   int pivotIndex = (right + left) / 2;\n",
    "   int temp;\n",
    "   temp = a[pivotIndex];\n",
    "   a[pivotIndex] = a[right];\n",
    "   a[right] = temp;\n",
    "}\n",
    " \n",
    "// Partition the array [left, right] with pivot initially on the right.\n",
    "// Return the index of the pivot after partition, all elements to the\n",
    "// left of pivot are smaller; while to the right are larger.\n",
    "int partition(int a[], int left, int right) {\n",
    "   int pivot = a[right];\n",
    "   int temp;  // for swapping\n",
    "   int storeIndex = left;\n",
    "      // Start the storeIndex from left, swap elements smaller than\n",
    "      //  pivot into storeIndex and increase the storeIndex.\n",
    "      // At the end of the pass, all elements up to storeIndex are\n",
    "      //  smaller than pivot.\n",
    "   for (int i = left; i < right; ++i) {  // exclude pivot\n",
    "      if (a[i] < pivot) {\n",
    "         // for tracing\n",
    "         print(a, left, right);\n",
    " \n",
    "         if (i != storeIndex) {\n",
    "            temp = a[i];\n",
    "            a[i] = a[storeIndex];\n",
    "            a[storeIndex] = temp;\n",
    "         }\n",
    "         ++storeIndex;\n",
    " \n",
    "         // for tracing\n",
    "         printf(\"=> \");\n",
    "         print(a, left, right);\n",
    "         printf(\"\\n\");\n",
    "      }\n",
    "   }\n",
    "   // Swap pivot and storeIndex\n",
    "   a[right] = a[storeIndex];\n",
    "   a[storeIndex] = pivot;\n",
    " \n",
    "   // for tracing\n",
    "   print(a, left, storeIndex - 1);\n",
    "   printf(\"{ %d }\",a[storeIndex]);\n",
    "   print(a, storeIndex + 1, right);\n",
    "   printf(\"\\n\");\n",
    "  \n",
    "   return storeIndex;\n",
    "}\n",
    " \n",
    "// Print the contents of the given array from left to right (inclusive)\n",
    "void print(const int a[], int left, int right) {\n",
    "     printf(\"{\");\n",
    "   for (int i = left; i <= right; ++i) {\n",
    "        printf(\"%d\",a[i]);\n",
    "      if (i < right)   printf(\",\");\n",
    "   }\n",
    "     printf(\"}\");\n",
    "}\n",
    "\n",
    "int main() {\n",
    "   const int SIZE = 8;\n",
    "   int a[8] = {49,38,65, 97,76, 13, 27,49};\n",
    " \n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "   printf(\"Sorting ...\\n\");\n",
    "   quickSort(a, SIZE);\n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "  \n",
    "}  \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/QuickSort ./demo/src/QuickSort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\QuickSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  4 Insertion Sort\n",
    "\n",
    "In brief, pass through the list.\n",
    "\n",
    "For each element, compare with `all` **previous** elements and `insert` it at the correct `position` by shifting the other elements. \n",
    "\n",
    "> 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。\n",
    "\n",
    "![insertionsort](./img/ds/insertsort.jpg)\n",
    "\n",
    "Here is some **pseudocode**\n",
    "\n",
    "```cpp\n",
    "for i <- 1 to length(A) do\n",
    "    key <- A[i]\n",
    "    j <- i - 1\n",
    "    while j >= 0 and  A[j] > key do\n",
    "          A[j+1] <- A[j]\n",
    "          j <- j - 1\n",
    "    end while\n",
    "    A[j+1] <- key\n",
    "end for \n",
    "```\n",
    "**Time complexity**\n",
    "\n",
    "The outer loop executes $n−1$ times.\n",
    "\n",
    "In the **worst** case, when `all the data are out of order`, the inner loop iterates \n",
    "\n",
    "* `once` on the `first` pass through the outer loop,\n",
    "\n",
    "* `twice` on the `second` pass, and so on, \n",
    "\n",
    "$$1+2+...+(n-1)=\\frac{1}{2}n^2-\\frac{1}{2}n$$\n",
    "\n",
    "for a total of $\\frac{1}{2}n^2-\\frac{1}{2}n$\n",
    "\n",
    "Thus, the worst-case behavior of insertion sort is $O(n^2)$. The insertion sort is  not efficient\n",
    "\n",
    ">But if the more items in the list that are in **order**, the **better** insertion sort gets\n",
    ">\n",
    ">* In the **best case** of a **sorted** list, the sort’s behavior is linear $O(n)$.\n",
    "\n",
    "In the **average** case, however, insertion sort is still quadratic $O(n^2)$.\n",
    "\n",
    "                                                                                 \n",
    "**Space complexity**\n",
    "\n",
    " in-place(原址) sorting algorithm: $O(1)$\n",
    "\n",
    "> pseudocode in LaTex: https://mirrors.cqu.edu.cn/CTAN/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf\n",
    ">\n",
    ">![latex-insertionsort.png](./img/ds/latex-insertionsort.png)\n",
    ">```latex\n",
    ">\\begin{algorithm}\n",
    "    \\caption{Insertion Sort}\n",
    "    \\begin{algorithmic}[1]\n",
    "        \\Function{Insertion-Sort}{$Array$}\n",
    "        \\For{$i = 1 \\to Array.length()$}\n",
    "        \\State $key \\gets Array[i]$\n",
    "        \\State $j \\gets i - 1$\n",
    "        \\While{$j >= 0 \\quad and \\quad A[j] > key$}\n",
    "           \\State $Array[j+1] \\gets  Array[j]$\n",
    "            \\State $ j \\gets  j - 1$\n",
    "        \\EndWhile\n",
    "        \\State $Arrry[j+1] \\gets key$\n",
    "       \\EndFor \n",
    "        \\EndFunction\n",
    "    \\end{algorithmic}\n",
    "\\end{algorithm}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Insertionsort in python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(array):\n",
    "    i = 1\n",
    "    for i in range(len(array)):\n",
    "        itemToInsert = array[i]\n",
    "        j = i - 1\n",
    "        while j >= 0 and array[j]>itemToInsert:\n",
    "            array[j + 1] = array[j]\n",
    "            j -= 1\n",
    "        array[j + 1] = itemToInsert\n",
    "    return  array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array=[4, 3, 2, 10, 12, 1, 5, 6]\n",
    "sortearray=insertion_sort(array)\n",
    "print(sortearray)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Insertionsort in C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/InsertionSort.c\n",
    "/* \n",
    "  Sorting an array using Insertion Sort (InsertionSort.c) \n",
    "*/\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "\n",
    "void insertionSort(int a[], int size);\n",
    "void print(const int a[], int iMin, int iMax);\n",
    "\n",
    "// Sort the given array of size using insertion sort\n",
    "void insertionSort(int a[], int size)\n",
    "{\n",
    "   int temp; // for shifting elements\n",
    "   for (int i = 1; i < size; ++i)\n",
    "   {\n",
    "      // for tracing\n",
    "      print(a, 0, i - 1);    // already sorted\n",
    "      print(a, i, size - 1); // to be sorted\n",
    "      printf(\"\\n\");\n",
    "\n",
    "      // For element at i, insert into proper position in [0, i-1]\n",
    "      //  which is already sorted.\n",
    "      // Shift down the other elements\n",
    "      for (int prev = 0; prev < i; ++prev)\n",
    "      {\n",
    "         if (a[i] < a[prev])\n",
    "         {\n",
    "            // insert a[i] at prev, shift the elements down\n",
    "            temp = a[i];\n",
    "            for (int shift = i; shift > prev; --shift)\n",
    "            {\n",
    "               a[shift] = a[shift - 1];\n",
    "            }\n",
    "            a[prev] = temp;\n",
    "            break;\n",
    "         }\n",
    "      }\n",
    "   }\n",
    "}\n",
    "\n",
    "// Print the contents of the array in [iMin, iMax]\n",
    "void print(const int a[], int iMin, int iMax) {\n",
    "   printf(\"{\");\n",
    "   for (int i = iMin; i <= iMax; ++i) {\n",
    "      printf(\"%d\", a[i]);\n",
    "      if (i < iMax) printf(\",\");\n",
    "   }\n",
    "   printf(\"} \");\n",
    "}\n",
    "\n",
    "\n",
    "int main()\n",
    "{\n",
    "   const int SIZE = 8;\n",
    "   int a[] = {4, 3, 2, 10, 12, 1, 5, 6};\n",
    "\n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "   insertionSort(a, SIZE);\n",
    "   print(a, 0, SIZE - 1);\n",
    "   printf(\"\\n\");\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/InsertionSort ./demo/src/InsertionSort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!.\\demo\\bin\\InsertionSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 Bubble Sort \n",
    "\n",
    "In brief, we pass thru the list, compare `two adjacent` items and swap them if they are in the wrong order.\n",
    "\n",
    "Repeat the pass until no swaps are needed. \n",
    "\n",
    "1. Compare $A[0]$ and $A[1]$. If $A[0]$ is `bigger` than $A[1]$, swap the elements.\n",
    "\n",
    "2. Move to the next element, $A[1]$ (which might now contain the result of a swap from the previous step), and compare it with $A[2]$. If $A[1]$ is bigger than $A[2]$, swap the elements. Do this for every pair of elements until the end of the list.\n",
    "\n",
    "3. Do steps $1$ and $2$ $n$ times.\n",
    ">\n",
    ">重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。\n",
    ">\n",
    ">重复地进行走访数列的工作是直到没有再需要交换，也就是说该数列已经排序完成。\n",
    ">\n",
    ">这个算法的名字由来是因为越小/大的元素会经由交换慢慢\"浮\"到数列的顶端。\n",
    ">\n",
    "\n",
    "![bubblesort](./img/ds/bubblesort.png)\n",
    "\n",
    "**Here is the pseudocode**\n",
    "\n",
    "\n",
    "```cpp\n",
    "for i <- 1 to a.length() do\n",
    "    for j <- 0 to a.length()-i do\n",
    "        if a[j]>a[j+1] then\n",
    "            swap a[j] <-> a[j+1]\n",
    "        end if\n",
    "    end for\n",
    "end for  \n",
    "```\n",
    "**Time complexity**\n",
    "\n",
    "Bubble sort has a nested loop. the inner loop executes $\\frac{1}{2}n^2-\\frac{1}{2}n$ times for a list of size $n$.\n",
    "\n",
    ">$(n-1)+(n-2)+...+2+1=\\frac{1}{2}n^2-\\frac{1}{2}n$\n",
    "\n",
    "Bubble sort is not efficient with time complexity of $O(n^2)$.\n",
    "\n",
    "**Space complexity**\n",
    "\n",
    "in-place: $O(1)$\n",
    "\n",
    "> pseudocode in LaTex: https://mirrors.cqu.edu.cn/CTAN/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf\n",
    ">\n",
    ">![latexbubblesort](./img/ds/latex-bubblesort.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 bubble sort in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(array):\n",
    "    length = len(array)\n",
    "    for i in range(1,length):\n",
    "        # Last i elements are already in place\n",
    "        for j in range(0,length-i):\n",
    "            if array[j] > array[j+1]:\n",
    "                array[j], array[j+1] = array[j+1], array[j]\n",
    "        print(array)    \n",
    "    return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[24, 56, 17, 77, 31, 44, 55, 20, 93]\n",
      "[24, 17, 56, 31, 44, 55, 20, 77, 93]\n",
      "[17, 24, 31, 44, 55, 20, 56, 77, 93]\n",
      "[17, 24, 31, 44, 20, 55, 56, 77, 93]\n",
      "[17, 24, 31, 20, 44, 55, 56, 77, 93]\n",
      "[17, 24, 20, 31, 44, 55, 56, 77, 93]\n",
      "[17, 20, 24, 31, 44, 55, 56, 77, 93]\n",
      "[17, 20, 24, 31, 44, 55, 56, 77, 93]\n",
      "[17, 20, 24, 31, 44, 55, 56, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "array=[56, 24, 93, 17,77, 31, 44,55,20]\n",
    "sortedarray=bubble_sort(array)\n",
    "print(sortedarray)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Improved bubble sort in C\n",
    "\n",
    "We can make a minor adjustment to the bubble sort to `improve` its **best-case** performance to linear.\n",
    "\n",
    "* If **no swaps** occur during a pass through the main loop, then the list is **sorted**. \n",
    "\n",
    "We can track the presence of swapping with a `Boolean` flag and return from the function \n",
    "\n",
    ">`no swaps` can happen on any pass, and in the **best case** will happen on the **first** pass.\n",
    ">\n",
    ">* The **best case** complexity is $O(n)$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file ./demo/src/BubbleSort.c\n",
    "/* Sorting an array using Bubble Sort (BubbleSort.c) */\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "#include <stdbool.h>  \n",
    "\n",
    "void bubbleSort(int a[], int size);\n",
    "void print(const int a[], int size);\n",
    "\n",
    "// Sort the given array of size\n",
    "void bubbleSort(int a[], int size) \n",
    "{\n",
    "   bool done = false; // terminate if no more swap thru a pass\n",
    "   int temp;          // use for swapping\n",
    " \n",
    "    for (int i = 1; i < size; i++)\n",
    "    {   printf(\"PASS %d ...\\n \",i);\n",
    "        done = true;\n",
    "        // Last i elements are already in place\n",
    "        for (int j = 0; j < size - i; j++)\n",
    "        {\n",
    "            if (a[j] > a[j + 1])\n",
    "            {\n",
    "                print(a, size); // for tracing\n",
    "                temp = a[j];\n",
    "                a[j] = a[j + 1];\n",
    "                a[j + 1] = temp;\n",
    "                done = false; // swap detected, one more pass\n",
    "                printf(\"=> \");  // for tracing\n",
    "                print(a, size);\n",
    "                printf(\"\\n\");\n",
    "            }\n",
    "        }\n",
    "        if (done)  break;\n",
    "    }\n",
    "}\n",
    " \n",
    "// Print the contents of the given array of size\n",
    "void print(const int a[], int size) {\n",
    "   printf(\"{\");\n",
    "   for (int i = 0; i <= size-1; ++i) {\n",
    "      printf(\"%d\", a[i]);\n",
    "      if (i < size-1) printf(\",\");\n",
    "   }\n",
    "   printf(\"} \");\n",
    "}\n",
    "\n",
    "\n",
    "int main() {\n",
    "   const int SIZE = 9;\n",
    "   int a[] = {56, 24, 93, 17,77, 31, 44,55,20};\n",
    " \n",
    "   print(a, SIZE);\n",
    "   printf(\"\\n\");\n",
    "   bubbleSort(a, SIZE);\n",
    "   print(a, SIZE);\n",
    "   printf(\"\\n\");\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/BubbleSort ./demo/src/BubbleSort.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{56,24,93,17,77,31,44,55,20} \n",
      "PASS 1 ...\n",
      " {56,24,93,17,77,31,44,55,20} => {24,56,93,17,77,31,44,55,20} \n",
      "{24,56,93,17,77,31,44,55,20} => {24,56,17,93,77,31,44,55,20} \n",
      "{24,56,17,93,77,31,44,55,20} => {24,56,17,77,93,31,44,55,20} \n",
      "{24,56,17,77,93,31,44,55,20} => {24,56,17,77,31,93,44,55,20} \n",
      "{24,56,17,77,31,93,44,55,20} => {24,56,17,77,31,44,93,55,20} \n",
      "{24,56,17,77,31,44,93,55,20} => {24,56,17,77,31,44,55,93,20} \n",
      "{24,56,17,77,31,44,55,93,20} => {24,56,17,77,31,44,55,20,93} \n",
      "PASS 2 ...\n",
      " {24,56,17,77,31,44,55,20,93} => {24,17,56,77,31,44,55,20,93} \n",
      "{24,17,56,77,31,44,55,20,93} => {24,17,56,31,77,44,55,20,93} \n",
      "{24,17,56,31,77,44,55,20,93} => {24,17,56,31,44,77,55,20,93} \n",
      "{24,17,56,31,44,77,55,20,93} => {24,17,56,31,44,55,77,20,93} \n",
      "{24,17,56,31,44,55,77,20,93} => {24,17,56,31,44,55,20,77,93} \n",
      "PASS 3 ...\n",
      " {24,17,56,31,44,55,20,77,93} => {17,24,56,31,44,55,20,77,93} \n",
      "{17,24,56,31,44,55,20,77,93} => {17,24,31,56,44,55,20,77,93} \n",
      "{17,24,31,56,44,55,20,77,93} => {17,24,31,44,56,55,20,77,93} \n",
      "{17,24,31,44,56,55,20,77,93} => {17,24,31,44,55,56,20,77,93} \n",
      "{17,24,31,44,55,56,20,77,93} => {17,24,31,44,55,20,56,77,93} \n",
      "PASS 4 ...\n",
      " {17,24,31,44,55,20,56,77,93} => {17,24,31,44,20,55,56,77,93} \n",
      "PASS 5 ...\n",
      " {17,24,31,44,20,55,56,77,93} => {17,24,31,20,44,55,56,77,93} \n",
      "PASS 6 ...\n",
      " {17,24,31,20,44,55,56,77,93} => {17,24,20,31,44,55,56,77,93} \n",
      "PASS 7 ...\n",
      " {17,24,20,31,44,55,56,77,93} => {17,20,24,31,44,55,56,77,93} \n",
      "PASS 8 ...\n",
      " {17,20,24,31,44,55,56,77,93} \n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\BubbleSort "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 Sorting in Python\n",
    "\n",
    "### 6.1  The sorting algorithm in Python\n",
    "\n",
    "The sorting algorithm used in most Python implementations is called \n",
    "\n",
    "* <b>Timsort</b> ： https://en.wikipedia.org/wiki/Timsort\n",
    "\n",
    "The **key idea** is to take **advantage** of the fact that in a lot of data sets the data is <b>already partially sorted</b>. \n",
    "\n",
    "**Timsort**’s worst-case performance is the same as **merge** sort’s, but on average it performs considerably **better.**\n",
    "\n",
    "The standard implementation of sorting in most Python implementations runs in roughly $O(n*log(n))$ time, where $n$ is the length of the list.\n",
    "\n",
    "\n",
    "In most cases, the right thing to do is to use with Python\n",
    "\n",
    "\n",
    "* 1  method **list.sort** : takes a `list` as its first argument and **modifies** that list,sorts the list (ascending sort),\n",
    "    \n",
    "    \n",
    "* 2 function **sorted** : takes an `iterable` object (e.g., a list or a dictionary) as its first argument and returns a **new** sorted list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2  Stable Sort(稳定排序)\n",
    "\n",
    "Both the **list.sort** method and the sorted function provide <b>stable sorts</b>. \n",
    "\n",
    "A sorting algorithm is stable if it preserves the **original** order of elements with equal key values (where the key is the value the algorithm sorts by).\n",
    "\n",
    "![stable](./img/ds/stablesort.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sorted list: new list\n",
    "L = [3,5,2]\n",
    "print('sorted L(a new list)=',sorted(L))\n",
    "print('L=',L)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sorted dict\n",
    "# dict:iterable\n",
    "D = {'a':12, 'c':5, 'b':'dog'}\n",
    "print('sorted D(a new list)=',sorted(D))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D.sort()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* when the sorted function is applied to a dictionary, it returns a `sorted list of the keys` of the dictionary. \n",
    "\n",
    "* In contrast, when the sort method is applied to a dictionary, it causes an exception to be raised since there is no method dict.sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# list.sort in place\n",
    "L.sort()\n",
    "print('L(modified L)=',L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Both the **list.sort** method and the **sorted** function can have two additional parameters.\n",
    "\n",
    "* <b>key</b> parameter plays the same role as compare in our implementation of merge sort: it is used to <b>supply the comparison function</b> to be\n",
    "used.\n",
    "\n",
    "\n",
    "* <b>reverse</b> parameter specifies whether the list is to be sorted in <b>ascending or descending order</b>.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [[1,2,3], (3,2,1,0), 'abc']\n",
    "print(sorted(L, key = len, reverse = True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "sorts the elements of L in `reverse` order of `length` and prints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7 Performance Criteria\n",
    "\n",
    "There are several criteria to be used in evaluating a sorting algorithm:\n",
    "\n",
    "* **Running time**. Typically, an elementary sorting algorithm requires $O(N^2)$ steps to sort $N$ randomly arranged items. More sophisticated sorting algorithms require $O(NlogN)$ steps on average. Furthermore, some sorting algorithms are more sensitive to the nature of the input than others. Quicksort, for example, requires $O(NlogN)$ time in the average case, but requires O(N2) time in the worst case. \n",
    "\n",
    "\n",
    "* **Memory requirements**. The amount of **extra** memory required by a sorting algorithm is also an important consideration. **In-place(就地/原址)** algorithms are the most memory efficient, since they require practically no additional memory. **Out-place(外置/异地)** algorithms require sufficent memory for another copy of the input array. These are the most inefficient in terms of memory usage. \n",
    "\n",
    "\n",
    "* **Stability**. This is the ability of a sorting algorithm to **preserve the relative order**f equal keys in a file.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To choose a sorting algorithm for a particular problem, consider the running time, space complexity, and the expected format of the input list.\n",
    "\n",
    "![choosesort](./img/ds/choosesort.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Further Reading\n",
    "\n",
    "* 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版），人民邮电出版社（第2版）,2015年2月  \n",
    "\n",
    "\n",
    "* Mark Allen Weiss. Data Structures and Algorithm Analysis in C\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
